Unless otherwise indicated herein, the materials described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
A network can be modeled as a fabric of switches that route traffic. If the internal speedup of the switch fabric is one and the time is slotted, cell transfer is subjected to the unique pairing constraint that one cell can depart from an input and also one cell can arrive at one output in a time slot. As a result, scheduling is needed to compute the matching between inputs and outputs before cell transmission. With the rapid increase of real-time applications, such as video and voice, stricter requirements are imposed on scheduling algorithms, which are required to possess low computational complexity, and to achieve good performances in terms of throughput, delay, delay jitter and fairness.
Formerly, slot-by-slot matching algorithms such as maximum size matching (MSM) were proposed to maximize throughput performance in each time slot. These schemes typically compute the matching in each time slot based on the collected information of input queues and impose strict requirements on the computational complexity of matching algorithms, one of the major scalability issues in designing high-speed routers with a large switch size. In frame-based matching schemes for computing the input/output matching frame by frame, each frame is composed of a number of consecutive slots. These schemes reduce the frequency of computing the matching from every time slot to every frame.